package string;

/**
 * @description: 字符串排序算法：低位优先
 *
 * 算法分析：
 * 基于R个字符的字母表的N个长为W的字符串为键的元素，低位优先的字符串排序需要访问~7WN+3WR次数组，占用空间于N+R成正比
 *
 * 该算法等价于调用W轮键索引计数法，但是aux数组只初始化一回，所以得到如上的结果
 * @title: LSD
 * @author: zp
 * @date: 2022/2/15 20:40
 */
public class LSD {
    public static void sort(String[] a, int w) {
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];

        //开始循环进行键索引计数排序
        for (int d = w - 1; d >= 0; d--) {  //从低位开始进行

            int count[] = new int[R + 1];
            for (int i = 0; i < N; i++) {
                count[a[i].charAt(d) + 1] += 1;
            }
            for (int r = 0; r < R; r++) {
                count[r + 1] += count[r];
            }

            for (int i = 0; i < N; i++) {
                aux[count[a[i].charAt(d) + 1]++] = a[i];
            }

            for (int i = 0; i < N; i++) {
                a[i] = aux[i];
            }
        }
    }

}
